package leetcode.top100;

import java.awt.*;
import java.util.LinkedList;
import java.util.Queue;

/**
 *  可以优化，把visited数组省去，把访问过的岛屿值由1修改为0，就代表访问过。
 * 方式1：BFS
 * 方式2：DFS
 * 方式3：并查集
 *
 * @since 2019/12/15 0015 下午 1:53
 */
public class Code200_NumLands_岛屿数量 {

    public static void main(String[] args) {
        char[][] chars = {{'1', '0', '0'}, {'1', '1', '0'}, {'0', '1', '1'}};
        System.out.println(numIslands(chars));
    }

    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;

//        return dfs(grid);
        return bfs(grid);
    }


    private static int bfs(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                //如果没有访问并且是岛屿，则进行BFS。
                if (grid[i][j] == '1' && !visited[i][j]) {
                    Queue<Point> queue = new LinkedList<>();
                    //当前位置的坐标,转为一维的 i*col+j或者包装
                    queue.add(new Point(i, j));
                    //标记为访问
                    visited[i][j] = true;
                    while (!queue.isEmpty()) {
                        Point cur = queue.poll();
                        int x = cur.x;
                        int y = cur.y;
                        //把前后左右访问并入队
                        //访问前后左右
                        doVisit(x - 1, y, grid, visited, queue);
                        doVisit(x + 1, y, grid, visited, queue);
                        doVisit(x, y - 1, grid, visited, queue);
                        doVisit(x, y + 1, grid, visited, queue);
                    }
                    count++;
                }
            }
        }
        return count;
    }

    private static void doVisit(int x, int y, char[][] grid, boolean[][] visited, Queue<Point> queue) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || visited[x][y]) {
            return;
        }
        if (grid[x][y] != '1' || visited[x][y]) return;
        queue.offer(new Point(x, y));
        visited[x][y] = true;
    }

    private static int dfs(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    effect(i, j, grid, visited);
                    count++;
                }
            }
        }
        return count;
    }

    private static void effect(int i, int j, char[][] grid, boolean[][] visited) {
        //base case1
        if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0) {
            return;
        }
        //base case 2
        if (visited[i][j] || grid[i][j] != '1') return;
        //访问该位置
        assert !visited[i][j] && grid[i][j] == '1';
        visited[i][j] = true;
        //前后左右感染
        effect(i - 1, j, grid, visited);
        effect(i + 1, j, grid, visited);
        effect(i, j - 1, grid, visited);
        effect(i, j + 1, grid, visited);
    }

    //TODO 并查集. https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
}
